package com.tgy.programmer_code_interview_guide._01_stack_queue;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/19/21 11:29 AM
 *
 *  https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 */
public class _08_柱状图中最大的矩形_stack {

    public static int largestRectangleArea(int[] heights) {

        if (heights == null || heights.length == 0) {

            return 0;
        }

        Stack<Integer> stack = new Stack<>();

        int max = 0;

        int[] preIndexs = new int[heights.length];

        for (int i = 0; i < preIndexs.length; i++) {

            preIndexs[i] = -1;
        }

        for (int i = 0; i < heights.length; i++) {

            if (stack.isEmpty()) {

                stack.push(i);
                continue;
            }

            while (!stack.isEmpty()  && heights[stack.peek()] > heights[i]) {

                int preIndex = stack.pop();
                max= Math.max(max,(i - preIndexs[preIndex] - 1) * heights[preIndex]);
            }

            if (!stack.isEmpty()) {

                preIndexs[i] = stack.peek();
            }

            stack.push(i);
        }

        int len = heights.length;
        int index;
        while (!stack.isEmpty()) {

            index = stack.pop();
            max = Math.max(max,(len - preIndexs[index] - 1) * heights[index]);
        }

        return max;
    }

  public static void main(String[] args) {

      int max = largestRectangleArea(new int[]{2, 1, 1, 5, 2, 3});
      System.out.println(max);
  }
}
